package class34;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class MinNotSum {

    public static int unformedSum1(int[] arr){
        if (arr==null||arr.length==0){
            return -1;
        }

        //收集所有min~max的能得到的累加和
        Set<Integer> set = new HashSet<>();
        process(arr,0,0,set);

        int min = Integer.MAX_VALUE;
        int sum = 0;
        for (int i =0;i<arr.length;i++){
            min = Math.min(min,arr[i]);
            sum += arr[i];
        }
        for (int i = min+1;i<=sum;i++){
            if (!set.contains(i)){
                return i;
            }
        }
        return sum+1;
    }

    private static void process(int[] arr,int index,int sum,Set<Integer> set){
        //如果此时已经没有元素 可选
        if (index==arr.length){
            if (!set.contains(sum)){
                set.add(sum);
            }
            return;
        }
        //要当前元素
        process(arr,index+1,sum+arr[index],set);
        //不要当前元素
        process(arr,index+1,sum,set);
    }


    public static int unformedSum2(int[] arr){
        if (arr==null||arr.length==0){
            return -1;
        }
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int i =0;i<arr.length;i++){
            sum+=arr[i];
            min = Math.min(min,arr[i]);
        }
        Set<Integer> set = new HashSet<>();
        int cur = 0;
        boolean[][] dp = new boolean[arr.length][sum+1];
        for (int i =0;i<arr.length;i++){
            dp[i][0] = true;
        }
        dp[0][arr[0]] = true;
        for (int i =1;i<arr.length;i++){
            for (int j =1;j<=sum;j++){
                dp[i][j] = dp[i-1][j] ||
                        ((j-arr[i]>=0)?dp[i-1][j-arr[i]]:false);
            }
        }
        for (int j =min;j<=sum;j++){
            if (!dp[arr.length-1][j]){
                return j;
            }
        }
        return sum+1;
    }

    //已知arr中肯定有1这个数
    public static int unformedSum3(int[] arr){
        if (arr==null||arr.length==0){
            return 0;
        }
        Arrays.sort(arr);//O(N*logN)
        int range = 1;
        for (int i=1;i!=arr.length;i++){
            if (arr[i]>range+1){
                return range+1;
            }else {
                range += arr[i];
            }
        }
        return range+1;
    }

    public static int[] generateArray(int len,int maxValue){
        int[] res = new int[len];
        for (int i =0;i<res.length-1;i++){
            res[i] = (int)(Math.random()*maxValue)+1;
        }
        res[res.length-1] = 1;
        return res;
    }

    public static int[] copyArray(int[] arr){
        if (arr==null||arr.length==0){
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0;i<arr.length;i++){
            res[i] = arr[i];
        }
        return res;
    }

    public static void printArray(int[] arr){
        for (int i=0;i!=arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int len = 10;
        int maxValue = 30;
        int testTime = 100000;
        System.out.println("test begin!");
        for (int i =0;i<testTime;i++){
            int[] arr1 = generateArray(len,maxValue);
            int[] arr2 = copyArray(arr1);
            int[] arr3 = copyArray(arr1);
            int res1 = unformedSum1(arr1);
            int res2 = unformedSum2(arr2);
            int res3 = unformedSum3(arr3);
            if (res1 != res2 || res2 != res3){
                System.out.println("test Ops!");
                printArray(arr1);
                printArray(arr2);
                printArray(arr3);
                System.out.println(res1);
                System.out.println(res2);
                System.out.println(res3);
                break;
            }
        }
        System.out.println("test end!");
    }

}
